/*
 * @lc app=leetcode.cn id=372 lang=cpp
 *
 * [372] 超级次方
 */

// @lc code=start
#include <bits/stdc++.h>
using namespace std;
class Solution
{
public:
    const int MOD = 1337;

    /**
     * @brief 计算 base 的 10次方并对MOD取模
     *
     * @param base
     * @return long long
     */
    long long cal(long long base)
    {
        long long base1 = base * base;         //平方
        long long base2 = base1 * base1 % MOD; //四次方
        long long base3 = base2 * base2 % MOD; //八次方
        return (base3 * base1) % MOD;
    }

    long long cal2(long long *nums, const long long base, const int ex)
    {
        if (nums[ex] != 0)
            return nums[ex];

        int tmp = ex / 2;
        nums[tmp] = cal2(nums, base, tmp);
        nums[ex - tmp] = cal2(nums, base, ex - tmp);
        return nums[tmp] * nums[ex - tmp] % MOD;
    }

    long long cal(long long base, long long ex)
    {
        long long nums[10] = {0};
        nums[0] = 1;
        nums[1] = base % MOD;
        nums[2] = base * base % MOD;
        nums[ex] = cal2(nums, base, ex);
        return nums[ex];
    }

    int superPow(long long a, vector<int> &b)
    {
        a %= MOD;
        vector<long long> nums; //记录以a为低，以 10^0，10^1，10^2 为指数...
        const int m = b.size();

        nums.push_back(a);

        for (int i = 1; i <= m; i++)
        {
            nums.push_back(cal(nums[i - 1]));
        }

        long long ans = 1;
        for (int i = 0; i < b.size(); ++i)
        {
            ans = ans * cal(nums[m - 1 - i], b[i]) % MOD;
        }

        return ans % MOD;
    }
};

// int main()
// {
//     int a = 2;
//     vector<int> b = {3};
//     cout << Solution().superPow(a, b) << endl;
//     return 0;
// }

// @lc code=end
